package com.ronz.binarytree;

/**
 * @Description 线索化二叉树
 * @Author Ronz
 * @Date 2021/1/18 18:39
 * @Version 1.0
 */
public class No3_ThreadedBinaryTree {

    public static void main(String[] args) {
        NumNode node_1 = new NumNode(1);
        NumNode node_2 = new NumNode(3);
        NumNode node_3 = new NumNode(6);
        NumNode node_4 = new NumNode(8);
        NumNode node_5 = new NumNode(10);
        NumNode node_6 = new NumNode(14);

        node_1.left = node_2;
        node_2.left = node_4;
        node_2.right = node_5;

        node_1.right = node_3;
        node_3.left = node_6;

        ThreadedBinaryTree tree = new ThreadedBinaryTree(node_1);
        tree.threadedNodes();
        tree.listNodes();
    }
}

/**
 * 线索化二叉树
 */
class ThreadedBinaryTree{
    private NumNode root;   // 根节点
    private NumNode pre = null;    // 当前节点的前驱

    public ThreadedBinaryTree(NumNode node){
        this.root = node;
    }

    // 遍历打印线索化的树
    public void listNodes(){
        NumNode node = root;
        while (node != null){
            // 首先到左树叶
            while (node.leftType == 0){
                node = node.left;
            }
            System.out.println(node);   // 打印树叶

            while (node.rightType == 1){
                node = node.right;
                System.out.println(node);
            }
            node = node.right;
        }

    }

    // 中序线索化二叉树的重载方法
    public void threadedNodes(){
        threadedNodes(root);
    }

    // 中序线索化二叉树
    public void threadedNodes(NumNode node){
        if (node == null){
            return;
        }
        // 先线索化左子树
        threadedNodes(node.left);
        // 线索化
        // 处理当前节点的左指针
        if (node.left == null){  // 如果左指针指向为空
            node.left = pre;   // 让当前节点的左指针指向前驱节点
            node.leftType = 1;  // 设置左指针指向的类型为前驱
        }
        // 处理前驱的右指针
        if (pre != null && pre.right == null){
            pre.right = node;   // 让前驱节点的右指针指向当前节点
            pre.rightType = 1;  // 设置前驱节点的右指针类型为后继
        }
        pre = node; // 处理完后，前驱指针要指向节点自己，接下来节点自己被下一个结点替代
        // 最后线索化右子树
        threadedNodes(node.right);
    }

}

/**
 * 二叉树结点
 */
class NumNode{
    int num;
    NumNode left;   // 左指针
    NumNode right;  // 右指针
    int leftType;   // 左指针类型：0-指向子树 1-指向前驱
    int rightType;  // 右指针类型：0-指向子树 1-指向后继

    public NumNode(int num){
        this.num = num;
    }

    @Override
    public String toString() {
        return "NumNode{" +
                "num=" + num +
                '}';
    }
}
